from collections import namedtuple
try:
    from commonfuncs.isrootN import isSquare
except:
    from isrootN import isSquare


def continuedfractionsSQRT(n: int) -> list:
    '''
    next two kind methods clash
    continuedfractionsSQRT2() is perfectly accurate, but is slower.
    '''
    return _continuedfractionsSQRT2(n)


def _continuedfractionsSQRT1(n) -> list:
    '''
    return continued fractions of sqrt(n)

    if ai == 2*res[0]: break
    '''

    if not isinstance(n, int) or n < 0:
        raise ValueError('n must be non-negative integer.')

    rest = n**0.5
    if isSquare(n):
        # print(f'sqrt({n}) = {int(n**0.5)} is not irrational number.')
        return [int(rest), tuple()]

    a0 = int(rest)

    res = [a0]
    rest = 1/(rest - a0)

    while True:
        ai = int(rest)
        res.append(ai)
        if ai == 2*res[0]:
            break

        rest = 1/(rest - ai)

    return [res[0], tuple(res[1:])]


def _continuedfractionsSQRT2(n: int) -> list:
    '''
    In order to filling the potential gap of continuedfractionsSQRT1(), 
    we re-realize div() operates

    e.g.  1 + (sqrt(23) - 3)/7 ----> (x=1, a=3, b=7)

    if (ai, rest) in res: break  # find period

    continuedfractionsSQRT2() is perfectly accurate.
    '''

    if not isinstance(n, int) or n < 0:
        raise ValueError('n must be non-negative integer.')

    if isSquare(n):
        # print(f'sqrt({n}) = {int(n**0.5)} is not irrational number.')
        return [int(n**0.5), tuple()]

    EXP = namedtuple('EXP', ['x', 'a', 'b'])

    rest = EXP(x=0, a=0, b=1)
    res = []  # [(ai,rest)]

    while True:
        ai = int(rest.x + (n**0.5 - rest.a)/rest.b)

        # rest = 1/(rest - ai)
        tmp = rest.a + ai*rest.b - rest.x*rest.b
        # b = (n - tmp**2)//rest.b
        # why must be exact division ?
        b = (n - tmp**2)/rest.b
        if b != int(b):
            # never come in theoretically
            raise ValueError(f'continuedfractionsSQRT({n}) Error!')
        b = int(b)
        result = (n**0.5 + tmp)/b
        x = int(result)
        a = x*b - tmp
        rest = EXP(x, a, b)

        if (ai, rest) in res:
            # find period
            break
        else:
            res.append((ai, rest))

    res = [ar[0] for ar in res]
    return [res[0], tuple(res[1:])]


if __name__ == '__main__':

    print(_continuedfractionsSQRT1(13), _continuedfractionsSQRT2(13))

    num = 1
    while num < 1000:
        if _continuedfractionsSQRT1(num) != _continuedfractionsSQRT2(num):
            print(f'Two kind methods clash, such as, {num}:\n')
            print(_continuedfractionsSQRT1(num))
            print('*'*87)
            print(_continuedfractionsSQRT2(num))
            break
        num += 1

    # 139 clash

    print('*'*87)
    for i in range(1,100):
        print(f'{i}---{continuedfractionsSQRT(i)}')

    # import cProfile
    # cProfile.run('continuedfractionsSQRT(991)')
